package LeetCode1;

import java.util.LinkedList;
import java.util.Queue;

//路径总和
public class Num112 {
    //解题思想：目标值反着一层一层减节点值，当走到根节点时目标值剩下的值，则等于根节点值
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //递归
//        if (root == null) {
//            return false;
//        }
//        //走到根节点判断
//        if(root.left == null && root.right == null) {
//            return targetSum == root.val;
//        }
//        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
        //非递归
        if (root == null) {
            return false;
        }
        //定义两个队列，一个用来记录节点，一个记录走到所在节点值总和
        Queue<TreeNode> queueRoot = new LinkedList<>();
        Queue<Integer> queueVal = new LinkedList<>();
        queueRoot.offer(root);
        queueVal.offer(root.val);
        while (!queueRoot.isEmpty()) {
            TreeNode cur = queueRoot.poll();
            int temp = queueVal.poll();
            if (cur.left == null && cur.right == null) {
                if (temp == targetSum) {
                    return true;
                }
                continue;
            }
            if (cur.left != null) {
                queueRoot.offer(cur.left);
                queueVal.offer(cur.left.val+temp);
            }
            if (cur.right != null) {
                queueRoot.offer(cur.right);
                queueVal.offer(cur.right.val+temp);
            }
        }
        return false;
    }
}
